#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define EMPTY_SYMBOL '.'
#define SUDOKU_SIZE 9

/**
 * @brief Check if current val match the board
 *
 * @param board
 * @param i
 * @param j
 * @param val
 *
 * @return 
 */
bool check(char** board, int i, int j, int val) {
    int hash[SUDOKU_SIZE] = {0};

    int iter, iteri, iterj;

    // check row
    for(iter=0;iter<SUDOKU_SIZE;iter++) {
        if(board[i][iter] != EMPTY_SYMBOL)
            hash[board[i][iter]-1-'0'] = 1;
    }

    // check column
    for(iter=0;iter<SUDOKU_SIZE;iter++) {
        if(board[iter][j] != EMPTY_SYMBOL)
            hash[board[iter][j]-1-'0'] = 1;
    }

    // check grid
    int grid_pivot, pivot_i, pivot_j;

    grid_pivot = j%3;
    if(0 == grid_pivot) {
        // left
        pivot_j = j;
    } else if(1 == grid_pivot) {
        // center
        pivot_j = j-1;
    } else {
        // right
        pivot_j = j-2;
    }

    grid_pivot = i%3;
    if(0 == grid_pivot) {
        // up
        pivot_i = i;
    } else if(1 == grid_pivot) {
        // center
        pivot_i = i-1;
    } else {
        // down
        pivot_i = i-2;
    }

    //printf("Grid corner : (%d, %d)\n", pivot_i, pivot_j);
    for(iteri=0;iteri<3;iteri++) {
        for(iterj=0;iterj<3;iterj++) {
            if(board[pivot_i+iteri][pivot_j+iterj] != EMPTY_SYMBOL) {
                hash[board[pivot_i+iteri][pivot_j+iterj]-1-'0'] = 1;
            }
        }
    }

    /*
       for(iter=0;iter<SUDOKU_SIZE;iter++) {
       printf("%d\t", hash[iter]);
       }
       printf("\n");
       */

    return (hash[val-1] == 0);
}

bool solve(char** board, int iter, int boardRowSize, int boardColSize) {
    int maxIter = boardRowSize*boardColSize-1;
    if(iter > maxIter) {
        // complete whole sudoku
        return true;
    }

    int i = iter/boardRowSize;
    int j = iter%boardColSize;
    //printf("Current pos iter[%d] : (%d,%d)\n", iter, i, j);

    if(board[i][j] == EMPTY_SYMBOL) {
        int val;
        for(val=1; val<=SUDOKU_SIZE; val++) {
            if(check(board, i, j, val)) {
                board[i][j] = val+'0';
                if(solve(board, iter+1, boardRowSize, boardColSize)) {
                    return true;
                }
                board[i][j] = EMPTY_SYMBOL;
            }
        }
    } else {
        return solve(board, iter+1, boardRowSize, boardColSize);
    }
    return false;
}

void solveSudoku(char** board, int boardRowSize, int boardColSize) {
    bool ret = solve(board, 0, boardRowSize, boardColSize);
}

void print_sudoku(char** board) {
    int i,j;
    for(i=0;i<SUDOKU_SIZE;i++) {
        for(j=0;j<SUDOKU_SIZE;j++) {
            printf("%c  ", board[i][j]);
        }
        printf("\n");
    }
}

int main() {
    char** board = (char**)malloc(sizeof(char*)*SUDOKU_SIZE);
    int i;
    for(i=0;i<SUDOKU_SIZE;i++) {
        board[i] = (char*)malloc(sizeof(char)*SUDOKU_SIZE);
    }

    char* tmp_board0 = "53..7....";
    char* tmp_board1 = "6..195...";
    char* tmp_board2 = ".98....6.";
    char* tmp_board3 = "8...6...3";
    char* tmp_board4 = "4..8.3..1";
    char* tmp_board5 = "7...2...6";
    char* tmp_board6 = ".6....28.";
    char* tmp_board7 = "...419..5";
    char* tmp_board8 = "....8..79";

    memcpy(board[0], tmp_board0, SUDOKU_SIZE);
    memcpy(board[1], tmp_board1, SUDOKU_SIZE);
    memcpy(board[2], tmp_board2, SUDOKU_SIZE);
    memcpy(board[3], tmp_board3, SUDOKU_SIZE);
    memcpy(board[4], tmp_board4, SUDOKU_SIZE);
    memcpy(board[5], tmp_board5, SUDOKU_SIZE);
    memcpy(board[6], tmp_board6, SUDOKU_SIZE);
    memcpy(board[7], tmp_board7, SUDOKU_SIZE);
    memcpy(board[8], tmp_board8, SUDOKU_SIZE);

    print_sudoku(board);

    solveSudoku(board, SUDOKU_SIZE, SUDOKU_SIZE);

    print_sudoku(board);

    // free board
    for(i=0;i<SUDOKU_SIZE;i++) {
        free(board[i]);
    }
    free(board);
    return 0;
}
